package org.xingole.daily;

import java.util.ArrayList;
import java.util.HashMap;

public class TheTwoSneakyNumbersOfDigitville {
    public int[] getSneakyNumbers(int[] nums) {
        /*
         * Approach 1: Hash Table
         * 
         * Use a hash table to count the numbers that appear twice in nums, and return the result.
         */
        var res   = new ArrayList<Integer>();
        var count = new HashMap<Integer, Integer>();
        for (int num : nums) {
            int c = count.getOrDefault(num, 0) + 1;
            count.put(num, c);

            if (c == 2) {
                res.add(num);
            }
        }

        return res.stream().mapToInt(Integer::intValue).toArray();
    }

    public int[] getSneakyNumbers2(int[] nums) {
        /*
         * Approach 2: Bitwise Operations
         * 
         * We XOR all the numbers in nums with all the numbers from 0 to n - 1. The result is the
         * XOR of the two extra numbers, denoted as y.
         * 
         * The lowest differing bit between these two numbers can be found using lowBit = y & -y.
         * 
         * Using this bit, we divide all the numbers in nums and the numbers from 0 to n - 1 into
         * two groups, then compute the XOR of each group. The results are the two missing numbers.
         */
        int n = nums.length - 2;
        int y = 0;
        for (int x : nums) {
            y ^= x;
        }

        for (int i = 0; i < n; i++) {
            y ^= i;
        }

        int lowBit = y & -y;
        int x1 = 0;
        int x2 = 0;
        for (int x : nums) {
            if ((x & lowBit) != 0) {
                x1 ^= x;
            } else {
                x2 ^= x;
            }
        }

        for (int i = 0; i < n; i++) {
            if ((i & lowBit) != 0) {
                x1 ^= i;
            } else {
                x2 ^= i;
            }
        }

        return new int[]{
            x1, 
            x2 
        };
    }
}
